§ 1.1 Field of the Invention
The present invention concerns detecting and diagnosing errors in connections, such as label-switched paths, that prevent user traffic from being delivered.
§ 1.2 Description of Related Art
The description of art in this section is not, and should not be interpreted to be, an admission that such art is prior art to the present invention. Although one skilled in the art will be familiar with networking, circuit switching, packet switching, label switched paths, and protocols such as RSVP and LDP, each is briefly introduced below for the convenience of the less skilled reader. More specifically, circuit switched and packet switched networks are introduced in § 1.2.1. The need for label switched paths, their operation, and their establishment are introduced in §§ 1.2.2-1.2.4 below. Finally, “failures” in a label switched path, as well as typical failure responses, are introduced in § 1.2.5 below.
§ 1.2.1 Circuit Switched Networks and Packet Switched Networks
Circuit switched networks establish a connection between hosts (parties to a communication) for the duration of their communication (“call”). The public switched telephone network (“PSTN”) is an example of a circuit switched network, where parties to a call are provided with a connection for the duration of the call. Unfortunately, many communications applications, circuit switched networks use network resources inefficiently. Consider for example, the communications of short, infrequent “bursts” of data between hosts. Providing a connection for the duration of a call between such hosts simply wastes communications resources when no data is being transferred. The desire to avoid such inefficiencies has lead to the development of packet switched networks.
Packet switched networks forward addressed data (referred to as “packets” in the specification below without loss of generality), typically on a best efforts basis, from a source to a destination. Many large packet switched networks are made up of interconnected nodes (referred to as “routers” in the specification below without loss of generality). The routers may be geographically distributed throughout a region and connected by links (e.g., optical fiber, copper cable, wireless transmission channels, etc.). In such a network, each router typically interfaces with (e.g., terminates) multiple links.
Packets traverse the network by being forwarded from router to router until they reach their destinations (as typically specified by so-called layer-3 addresses in the packet headers). Unlike switches, which establish a connection for the duration of a “call” or “session” to send data received on a given input port out on a given output port, routers determine the destination addresses of received packets and, based on these destination addresses, determine, in each case, the appropriate link on which to send them. Routers may use protocols to discover the topology of the network, and algorithms to determined the most efficient ways to forward packets towards a particular destination address(es). Since the network topology can change, packets destined for the same address may be routed differently. Such packets can even arrive out of sequence.
§ 1.2.2 The Need for Label Switched Paths
In some cases, it may be considered desirable to establish a fixed path through at least a part of a packet switched network for at least some packets. More specifically, merely using known routing protocols (e.g., shortest path algorithms) to determine paths is becoming unacceptable in light of the ever-increasing volume of Internet traffic and the mission-critical nature of some Internet applications. Such known routing protocols can actually contribute to network congestion if they do not account for bandwidth availability and traffic characteristics when constructing routing (and forwarding) tables.
Traffic engineering permits network administrators to map traffic flows onto an existing physical topology. In this way, network administrators can move traffic flows away from congested shortest paths to a less congested path. Alternatively, paths can be determined autonomously, even on demand. Label-switching can be used to establish a fixed path from a head-end node (e.g., an ingress router) to a tail-end node (e.g., an egress router). The fixed path may be determined using known protocols such as RSVP or LDP. Once a path is determined, each router in the path may be configured (manually, or via some signaling mechanism) to forward packets to a peer (e.g., a “downstream” or “upstream” neighbor) router in the path. Routers in the path determine that a given set of packets (e.g., a flow) are to be sent over the fixed path (as opposed to being routed individually) based on unique labels added to the packets.
§ 1.2.3 Operations of Label Switched Paths
In one exemplary embodiment, the virtual link generated is a label-switched path (“LSP”). More specifically, recognizing that the operation of forwarding a packet, based on address information, to a next hop can be thought of as two steps-partitioning the entire set of possible packets into a set of forwarding equivalence classes (“FECs”), and mapping each FEC to a next hop. As far as the forwarding decision is concerned, different packets which get mapped to the same FEC are indistinguishable. In one technique concerning label switched paths, dubbed “multiprotocol label switching” (or “MPLS”), a particular packet is assigned to a particular FEC just once, as the packet enters the label-switched domain (part of the) network. The FEC to which the packet is assigned is encoded as a label, typically a short, fixed length value. Thus, at subsequent nodes, no further header analysis need be done—all subsequent forwarding over the label-switched domain is driven by the labels. Such FECs may be generalized such that particular ports, wavelengths, time slots, channels, etc. are used instead of labels.
FIG. 1 illustrates a label-switched path 110 across a network. Notice that label-switched paths 110 are simplex—traffic flows in one direction from a head-end label-switching router (or “LSR”) 120 at an ingress edge to a tail-end label-switching router 130 at an egress edge. Generally, duplex traffic requires two label-switched paths—one for each direction. However, some protocols support bi-directional label-switched paths. Notice that a label-switched path 110 is defined by the concatenation of one or more label-switched hops, allowing a packet to be forwarded from one label-switching router (LSR) to another across the MPLS domain 110.
Recall that a label may be a short, fixed-length value carried in the packet's header to identify a forwarding equivalence class (or “FEC”). Recall further that a FEC is a set of packets that are forwarded over the same path through a network, sometimes even if their ultimate destinations are different. At the ingress edge of the network, each packet is assigned an initial label (e.g., based on all or a part of its layer 3 destination address). More specifically, referring to the example illustrated in FIG. 2, an ingress label-switching router 210 interprets the destination address 220 of an unlabeled packet, performs a longest-match routing table lookup, maps the packet to an FEC, assigns a label 230 to the packet and forwards it to the next hop in the label-switched path.
In the MPLS domain, the label-switching routers (LSRs) 220 ignore the packet's network layer header and simply forward the packet using label-swapping. More specifically, when a labeled packet arrives at a label-switching router (LSR), the input port number and the label are used as lookup keys into an MPLS forwarding table. When a match is found, the forwarding component retrieves the associated outgoing label, the outgoing interface (or port), and the next hop address from the forwarding table. The incoming label is replaced with the outgoing label and the packet is directed to the outgoing interface for transmission to the next hop in the label-switched path. FIG. 2 illustrates such label-switching by label-switching routers (LSRs) 220a and 220b. 
When the labeled packet arrives at the egress label-switching router, if the next hop is not a label-switching router, the egress label-switching router discards (“pops”) the label and forwards the packet using conventional (e.g., longest-match IP) forwarding. FIG. 2 illustrates such label popping and IP forwarding by egress label-switching router 240.
§ 1.2.4 Establishing Label Switched Paths
In the example illustrated with reference to FIG. 2, each label-switching router had appropriate forwarding labels. However, these labels must be provided to the label-switching routers in some way.
There are two basic types of LSPs—static LSPs and protocol (e.g., LDP, RSVP, BGP) signaled LSPs. Although each type of LSP is known to those skilled in the art, each is introduced below for the reader's convenience.
With static LSPs, labels are manually assigned on all routers involved in the path. No signaling operations by the nodes are needed.
With LDP signaled LSPs, routers establish label-switched paths (LSPs) through a network by mapping network-layer routing information directly to data link layer switched paths. LDP operates in a hop-by-hop fashion as opposed to RSVP's end-to-end fashion. More specifically, LDP associates a set of destinations (route prefixes and router addresses) with each data link LSP. This set of destinations is called the Forwarding Equivalence Class (“FEC”). These destinations all share a common data link layer-switched path egress and a common unicast routing path. Each router chooses the label advertised by the next hop for the FEC and splices it to the label it advertises to all other routers. This forms a tree of LSPs that converge on the egress router.
With RSVP signaled LSPs, an ingress (i.e., head-end) router is configured. The head-end router uses (e.g., explicit path and/or path constraint) configuration information to determine the path. The egress (i.e., tail-end) and intermediate routers accept signaling information from the ingress (i.e., head-end) router. RSVP signaled LSPs maintain “soft-state” connections; meaning an RSVP signaled LSP is refreshed periodically or it is torn down. Therefore, the routers of the LSP set up and maintain the LSP cooperatively through the use of path signaling messages such as PATH messages and RESV messages.
PATH messages are sent from the ingress router to the egress router and follow the path of the LSP. RESV messages originate from the egress router, and is delivered hop-by-hop back towards the ingress router. As a PATH message travels the path of an LSP, it takes the IP address of the router it was transmitted from and stores it in the router to which it is sent. This “IP trail” left by the PATH message is used by RESV messages to return back through the LSP path. Any errors encountered when establishing and maintaining an LSP are reported back to the ingress (i.e., head-end) router.
An LSP may be considered to have two planes, a control plane and a data plane. In an RSVP signaled LSP, the PATH and RESV messages that are used to set up and maintain the LSP are transmitted on the control plane using IP addresses, and user traffic is transmitted on the data plane using labels.
§ 1.2.5 “Failures” in a Label Switched Path
In various situations the forwarding information 220 of the forwarding component 210 of intermediate label-switching routers (LSRs) may become corrupted, e.g., OUT label 230 is stored as “3” instead of “5”. In this situation, data leaving LSR 210 will be “black-holed”. That is, when LSR 220a receives the packet with an IN label of “3” it will either discard it or transmit the packet along an LSP other than the desired LSP.
Since the control plane uses IP addresses to route its messages, the control plane is still active and does not recognize the error. Therefore, the ingress LSR may continue to transmit data through the broken LSP.
If an ingress LSR continuously fails to deliver data through a given LSP, that LSP may be suspected of being down. It is desirable to provide a tool that would detect, within a reasonable amount of time, if a suspected LSP is actually down. In the art, there is no practical and quick solution known to detect the liveliness of the data plane of an LSP. Presently, if an LSP is suspected of being down, users perform manual memory dumps along several LSPs, examining the labeling information of the control plane and the data plane of the LSPs, to discover which LSP was broken. This procedure can be very time consuming and may not be a practical solution because of the length of time needed to locate the problem.